Computational geometry

In computer science, computational geometry is the study of algorithms to solve problems stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and the study of such problems is also considered to be part of computational geometry.

The main impetus for the development of computational geometry as a discipline was progressing in computer graphics, computer-aided design, and manufacturing (CAD/CAM), but many problems in computational geometry are classical in nature.

Other important applications of computational geometry include robotics (motion planning and visibility problems), geographic information systems (GIS) (geometrical location and search, route planning), integrated circuit design (IC geometry design and verification), computer-aided engineering (CAE) (programming of numerically controlled (NC) machines).

The three main branches of computational geometry are:

• Combinatorial computational geometry, also called algorithmic geometry, which deals with geometric objects as discrete entities.
• Numerical geometry, also called machine geometry, computer-aided geometric design (CAGD), or geometric modeling, which deals primarily with representing real-world objects in forms suitable for computer computations in CAD /CAM systems. This branch may be seen as a further development of descriptive geometry and is often considered a branch of computer graphics and/or CAD, whereas the former branch is often called simply computational geometry.
• Non-numerical geometry, which studies and develops non-numerical geometrical algorithms. This is the oldest branch of computational geometry which goes back to geometric constructions with the help of ruler and compass. Algorithms of geometric constructions are the soul and the origin of geometry and are not numerical in nature. Although until recently such constructions could be performed with the help of a ruler and compass only, two decades ago new means of geometric constructions emerged. These were various optical devices capable of manipulating images of geometrical figures, such as mirrors, beam splitters, holograms, etc. The observation that geometric constructions can be performed optically rather than with the help of ruler and compass laid in the foundation of "Optical Computational Geometry" put forward by Yevgeny Karasik in 1990.